/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode *slow = head, *ret = head; // slow最终指向待删节点的前驱，ret保存头节点
        for(int i = 0; i < n; ++i) // 快指针（head）先走n步
        {
            head = head->next;
        }
        if(head == nullptr) // 走到末尾，说明要删除的是头节点（链表长度恰好为n）
            return ret->next;
            
        while(head->next != nullptr) // 快慢指针同步移动，直到快指针到达最后一个节点
        {
            head = head->next;
            slow = slow->next;
        }
        slow->next = slow->next->next; // 删除slow的下一个节点（倒数第n个）
        return ret; // 返回原头节点
    }
};